COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	intro.pro[f84,jmc]	Introduction to DARPA proposal for Qlambda on parallel processors
C00011 ENDMK
C⊗;
intro.pro[f84,jmc]	Introduction to DARPA proposal for Qlambda on parallel processors

	This is a proposal for research in implementing
an extension of Lisp for parallel processing called Qlambda.
Qlambda (Gabriel and McCarthy 1984) allows the programmer
to specify tasks that may be performed in parallel by creating
queues of tasks.  The project involves acquiring a parallel
processor, developing Qlambda for it (with a subcontract), developing
a major application system for it (a variant of Macsyma), and
testing the performance of the application on substantial
symbolic computation tasks.

	It is generally agreed that the main hope for large increases in
computer speed, whether for numerical work or symbolic computation as in
artificial intelligence, lies in massive parallelism.  Projects are being
undertaken that will involve hundreds or even thousands of processors.
However, no-one has yet demonstrated the ability to make general purpose
use of even two processors on symbolic computation for a single problem.
Indeed even numerical computation on parallel processors has been
difficult, and there are no general purpose computation systems
that make good use of parallel processors in spite of more than
twenty years of work.  Therefore, it is important to explore a variety
of approaches to getting good performance from parallel processors
on a variety of problems.

	Our approach is queue-based multi-processing.  It has the
following features.

	1. Each processor can address the whole of memory, and
a processor may execute program anywhere in memory on data located
anywhere in memory.  This makes difficulty for the hardware designer,
we are running scared on programming, so we ask the help of the
hardware people.

	2. The programmer indicates when parallelism is possible
by using parallel constructions in the source language, which
is an extension of Lisp.  See (Gabriel and McCarthy 1984) for
a description of this language called Qlambda.

	3. When a program comes to a statement allowing
parallelism and decides (according to the computed value
of an allow-parallelism parameter in the statement) that
parallelism is to be invoked, it adds a collection of tasks
to a queue and starts on the first.  When a processor completes
a task it goes to the queue for its next task.  It may execute
some queue management code to decide what to do next.

	4. Basing parallelism on run-time queues means that
a program isn't written or compiled for any specific number
of processors.  The number available can even change during
the course of a computation.  Tasks need not be of similar
length, because a processor finishing a short task merely
takes another from the queue.

	5. While Qlambda is more fully described in the paper,
we mention just the statement  QLET here.  Its form is

	(QLET allow ((x1 arg1))
	               .
		       .
		       .
		   ((xn argn))
	    . body).


The parameter  {\it allow} is evaluated first.  If its value is
(), i.e. false, parallelism is not allowed and the QLET statement
behaves like an ordinary Common Lisp LET.  If the value is something
else and not EAGER, then a queue of tasks is set up to evaluate
arg1 ... argn, and the processor takes a task from the queue.  If
the value is EAGER, the processor sets up the queue and immediately
starts on evaluating {\it body}, suspending if it comes to a
variable whose value has not yet been computed.

	The point of exhibiting QLET here is that the parameter
{\it allow} is evaluated to determine whether parallelism is allowed.
Because Lisp (and symbolic computation generally) is highly recursive,
it can generate a large number of parallel tasks.  However, we need
only enough parallelism to keep our processors busy.  Therefore,
the expression {\it allow} should often be false.  Qlambda is designed
according to the idea that it is necessary to limit parallelism as
well as to instigate it.

	We believe that it is necessary to follow through on the
development and implementation of Qlambda by trying it out on
substantial applications.  These trials will most likely lead to
improvements in Qlambda and in the parallel processing hardware.
They may also determine whether it is possible to relax the requirement
that all memory be equally accessible to all processors, since
the hardware people find this expensive to implement.

	For this purpose, we have chosen a Macsyma-like system
as the target application.  Our reasons for choosing this rather
than an AI application are the following.

	1. Macsyma and similar systems like REDUCE and SMP use
a wide variety of algorithms each with its own inner loop and
each of which presents its own problems of parallelism.

	2. When a sufficient number of features have been implemented,
we can compare performance with algebraic computation systems running
on single processors.

	3. The task is definite enough to be readily defined
and supervised.  Some of our group are eager to undertake it.

	We are also thinking about possible AI applications, e.g.
to problem solving, but are not ready to decide on one.  In
addition, the parallel facility and Qlambda will be available
on the ARPAnet for others to try out.